"""
Title: 斐波纳契数列
Description: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。

两种递归解法：经典解法和优化解法
两种非递归解法：递推法和数组法
"""


def fibonacci_sequence(n, f1=1, f2=1):
    """
    求第n个斐波纳契数列值
    :param n:
    :return:
    """
    if n == 1:
        return f1
    if n == 2:
        return f2
    if n == 3:
        return f1 + f2
    return fibonacci_sequence(n - 1, f2, f1 + f2)


if __name__ == "__main__":
    print(fibonacci_sequence(1))
    print(fibonacci_sequence(2))
    print(fibonacci_sequence(3))
    print(fibonacci_sequence(4))
    print(fibonacci_sequence(5))
    print(fibonacci_sequence(6))
    print(fibonacci_sequence(7))
    print(fibonacci_sequence(8))
    print(fibonacci_sequence(30))  # 832040
    print(fibonacci_sequence(31))  # 1346269
    print(fibonacci_sequence(32))  # 2178309
    print(fibonacci_sequence(300))  # 222232244629420445529739893461909967206666939096499764990979600
